import time

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key
    return arr

def is_sorted(arr):
    return all(arr[i] <= arr[i + 1] for i in range(len(arr) - 1))

# 测试用例
test_cases = [
    [5, 2, 8, 1, 9, 3],
    [-3, 0, 1, 4, -1],
    [10, 9, 8, 7, 6, 5]
]

for case in test_cases:
    original = case.copy()
    start_time = time.time()
    result = insertion_sort(case)
    end_time = time.time()
    is_correct = is_sorted(result) and sorted(original) == result

    print(f"输入数组: {original}")
    print(f"输出数组: {result}")
    print(f"结果是否正确: {is_correct}")
    print(f"测试时间: {end_time - start_time} 秒")
    print("-" * 30)
